# 给一个二维列表，表示迷宫(0表示通道，1表示围墙)。给出算法，求一条走出迷宫的路径。
from collections import deque

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],

]

# 栈--深度优先搜索
# 用栈解决迷宫问题
# 基本思路:在一个迷宫节点(x,y)上,可以进行四个方向的探索:maze[x-1][y]上,maze[x][y+1]右,maze[x+1][y]下,maze[x][y-1]左
# 思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点。
# 方法：创建一个空栈，首先将入口位置进栈。当栈不空时循环：获取栈顶元素，寻找下一个可走的相邻方块，如果找不到可走的相邻方块，说明当前是死胡同，进行回溯。


# 四个方向寻路 x,y四个方向 上(x-1,y),右(x,y+1),下(x+1,y),左(x,y-1)
dirs = [
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y + 1),
    lambda x, y: (x + 1, y),
    lambda x, y: (x, y - 1)
]


# x1,y1相当于maze[x1][y1]这里的x,y和平面直角坐标系的是不一样的
def maze_path_stack(x1, y1, x2, y2):
    # 定义栈(列表类型)
    stack = []
    # 将开始的坐标用元祖存储起来，并放入栈中
    stack.append((x1, y1))
    # 如果栈内没有数据，循环结束
    while len(stack) > 0:
        # 当前的坐标
        curNode = stack[-1]
        # 表示现在已经走到终点了
        if curNode[0] == x2 and curNode[1] == y2:
            print('栈的路线是：', stack)
            return True

        # 对当前坐标的四个方向坐标点进行历比较
        for d in dirs:
            nextNode = d(curNode[0], curNode[1])
            # 如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                # 将已经添加的节点设置为2表示该节点已经走过
                maze[nextNode[0]][nextNode[1]] = 2
                break
        else:
            # 如果一个节点都没有能走的都没也标记为走过的
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()
    else:
        print('没有路可走')
        return False


# maze_path_stack(1, 1, 8, 8)


# 队列实现广度优先
# 队列解决迷宫寻路问题
# 思路：从一个节点开始，寻找所有下面能继续走的点。继续寻找，直到找到出口
# 方法：创建一个空队列，将起点位置进队。在队列不为空时循环：出队一次。如果当前位置为出口，则算法结束；否则找出当前方块的4个相邻方块中可走的方块，全部进队。
def maze_path_queue(x1, y1, x2, y2):
    # 创建队列
    queue = deque()
    # 添加初始位置
    queue.append((x1, y1, -1))
    # 记录入队之后的节点
    path = []
    while len(queue) > 0:
        # 起点出队，将起点存入变量curNode中
        curNode = queue.pop()
        # 将出队的节点放入path中
        path.append(curNode)
        # 抵达终点
        if curNode[0] == x2 and curNode[1] == y2:
            print('path', path)
            real_path = []
            x, y, i = path[-1]
            real_path.append((x, y))
            while i >= 0:
                node = path[i]
                real_path.append(node[0:2])
                print('i = ', i)
                i = node[2]
            real_path.reverse()
            print(real_path)
            return True
        for d in dirs:
            # 当前节点的上，左，下，右
            nextNode = d(curNode[0], curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                # 将可以走通的节点存入
                queue.append((nextNode[0], nextNode[1], len(path) - 1))
                # 标记存入queue的节点
                maze[nextNode[0]][nextNode[1]] = 2
    else:
        print('没有路')
        return False


maze_path_queue(1, 1, 8, 8)
# 总结
# 栈解决迷宫问题占用内存相对较小，但用栈找到的出路只是所有出路中的其中一条，具体是哪一条取决于dirs列表中上下左右的位置
# 队列解决迷宫问题找到的出路肯定是最短路径，但是相对而言队列会比较占内存
